package service.week04.leetcode.editor.cn;
//设计一个算法，找出二叉搜索树中指定节点的“下一个”节点（也即中序后继）。 
//
// 如果指定节点没有对应的“下一个”节点，则返回null。 
//
// 示例 1: 
//
// 输入: root = [2,1,3], p = 1
//
//  2
// / \
//1   3
//
//输出: 2 
//
// 示例 2: 
//
// 输入: root = [5,3,6,2,4,null,null,1], p = 6
//
//      5
//     / \
//    3   6
//   / \
//  2   4
// /   
//1
//
//输出: null 
// Related Topics 树 深度优先搜索 二叉搜索树 二叉树 
// 👍 68 👎 0

import model.TreeNode;

public class P_04_06SuccessorLcci {
    public static void main(String[] args) {
        Solution solution = new P_04_06SuccessorLcci().new Solution();
        // TO TEST
    }
    //leetcode submit region begin(Prohibit modification and deletion)

    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     * int val;
     * TreeNode left;
     * TreeNode right;
     * TreeNode(int x) { val = x; }
     * }
     */
    class Solution {
        public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
            TreeNode succ = findSucc(root, p.val);
            return succ;

        }

        private TreeNode findSucc(TreeNode root, int val) {
            TreeNode curr = root;
            TreeNode res = null;
            while (curr != null) {
                if (curr.val > val) {
                    //经过的点上的最小值
                    if (res == null || res.val > curr.val) {
                        res = curr;
                    }
                }
                if (curr.val == val) {
                    //查询右子树
                    if (curr.right != null) {
                        curr = curr.right;
                        while (curr.left != null) {
                            curr = curr.left;
                        }
                        return curr;
                    }
                    break;
                }
                if (val < curr.val) {
                    curr = curr.left;
                } else {
                    curr = curr.right;
                }
            }
            return res;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}